// 一个盒子，二十黑，二十白。不放回取，取白球得一元，取黑球给一元（没钱就是负到），可随时停下不取。问如何设计算法得到每一步最好的决策：下一步继续玩还是停下？整体获利期望是多少？

#include <iostream>
#include <vector>
using namespace std;

vector<vector<float>> get_ans(int tw, int tb) {
    vector<vector<float>> rec(tw + 1, vector<float>(tb + 1));
    vector<vector<float>> judge(tw + 1, vector<float>(tb + 1)); // 包含停下不取的期望
    rec[0][0] = 0;
    judge[0][0] = 0;
    for (int n = 1; n <= tw; ++n) {
        rec[n][0] = rec[n - 1][0] + 1;
        judge[n][0] = rec[n][0];
    }
    for (int m = 1; m <= tb; ++m) {
        rec[0][m] = rec[0][m - 1] - 1;
        judge[0][m] = 0;
    }
    for (int n = 1; n <= tw; ++n) { // 剩下的白球
        for (int m = 1; m <= tb; ++m) { // 剩下的黑球
            rec[n][m] = (rec[n - 1][m] + 1) * n / (m + n) + (rec[n][m - 1] - 1) * m / (m + n);
            judge[n][m] = max(rec[n][m], n / (m + n) * judge[n - 1][m] + m / (m + n) * judge[n][m - 1]);
        }
    }
   
    return judge;
}

int main() {
    int tw = 20; // 总的白球
    int tb = 20; // 总的黑球
    vector<vector<float>> judge = get_ans(tw, tb);
    
    for (int i = 0; i <= tw; ++i) {
        for (int j = 0; j <= tb; ++j) {
            cout << judge[i][j] << " ";
        }
        cout << endl;
    }
}
